#include<iostream>
#include<queue>
#include"binarySearchTree.h"

// preorder traversal definition
template<class K>
void linkedBinaryTree<K>::preOrder(binaryTreeNode<K>* t) {
    if (t == nullptr) return;
    visit(t);
    preOrder(t->leftChild);
    preOrder(t->rightChild);
}

// Mid-order traversal definition
template<class K>
void linkedBinaryTree<K>::inOrder(binaryTreeNode<K>* t) {
    if (t == nullptr) return;
    inOrder(t->leftChild);
    visit(t);
    inOrder(t->rightChild);
}

// post-order traversal definition
template<class K>
void linkedBinaryTree<K>::postOrder(binaryTreeNode<K>* t) {
    if (t == nullptr) return;
    postOrder(t->leftChild);
    postOrder(t->rightChild);
    visit(t);
}

// sequence traversal definition
template<class K>
void linkedBinaryTree<K>::levelOrder(void (*theVisit)(binaryTreeNode<K>*)) {
    if (root == nullptr) return;
    std::queue<binaryTreeNode<K>*> q;
    q.push(root);
    while (!q.empty()) {
        binaryTreeNode<K>* node = q.front();
        q.pop();
        theVisit(node);
        if (node->leftChild) q.push(node->leftChild);
        if (node->rightChild) q.push(node->rightChild);
    }
}

template<class K>
void (*linkedBinaryTree<K>::visit)(binaryTreeNode<K>*) = nullptr;

template<class K,class E>
std::pair<const K, E>* binarySearchTree<K, E>::find(const K& theKey)const
{
    binaryTreeNode<std::pair<const K, E>>* p = root;
    while (p != nullptr)
    {
        if (p->element.first < theKey)
            p = p->rightChild;
        else if (p->element.first > theKey)
            p = p->leftChild;
        else
            return &p->element;
    }

    return nullptr;
}

template<class K,class E>
void binarySearchTree<K, E>::insert(const std::pair<const K, E>& thePair)
{
    binaryTreeNode<std::pair<const K, E>>* p = root;
    binaryTreeNode<std::pair<const K, E>>* pp = nullptr;

    while (p != nullptr)
    {
        pp = p;
        if (p->element.first > thePair.first)
            p = p->leftChild;
        else if (p->element.first < thePair.first)
            p = p->rightChild;
        else
            p->element.second = thePair.second;
    }

    auto newNode = new binaryTreeNode<std::pair<const K, E>>(thePair);
    if (root != nullptr)
    {
        if (pp->element.first > thePair.first)
            pp->leftChild = newNode;
        else if (pp->element.first < thePair.first)
            pp->rightChild = newNode;
    }
    else
        root = newNode;
    treeSize++;
}

template<class K,class E>
void binarySearchTree<K, E>::erase(const K& theKey)
{
    binaryTreeNode<std::pair<const K, E>>* p = root;
    binaryTreeNode<std::pair<const K, E>>* pp = nullptr;

    while (p != nullptr && p->element.frist == theKey)
    {
        pp = p;
        if (p->element.first > theKey)
            p = p->leftChild;
        else
            p = p->rightChild;
    }
    if (p == nullptr)
        return;

    if (p->leftChild != nullptr && p->rightChild != nullptr)
    {
        binaryTreeNode<std::pair<const K, E>>* s = p->leftChild;
        binaryTreeNode<std::pair<cosnt K, E>>* ps = nullptr;
        while (s != nullptr)
        {
            ps = s;
            s = s->rightChild;
        }

        auto q = new binaryTreeNode<std::pair<const K, E>>(s->element, p->leftChild, p->rightChild);
        if (pp == nullptr)
            root = q;
        else if (pp->leftChild == p)
            pp->leftChild = q;
        else
            pp->rightChild = q;

        if (ps == p)
            pp = q;
        else
            pp = ps;
        delete p;
        p = s;
    }

    binaryTreeNode<std::pair<const K, E>>* c;
    if (p->leftChild != nullptr)
        c = p->leftChild;
    else
        c = p->rightChild;
    if (p == root)
        root = c;
    else
    {
        if (p == pp->leftChild)
            pp->leftChild = c;
        else
            pp->rightChild = c;
    }
    delete p;
    treeSize--;
}